#pragma once
#include "Common.h"
#include "ObjectPool.h"



template <int BITS>
class TCMalloc_PageMap1 {
private:
	static const int LENGTH = 1 << BITS;
	void** array_;
public:
	typedef uintptr_t Number;

	explicit TCMalloc_PageMap1() {
		// array_ = reinterpret_cast<void**>((*allocator)sizeof(void*) << BITS));
		size_t size = sizeof(void*) << BITS;
		size_t alignSize = SizeClass::_RoundUp(size, 1 << PAGE_SHIFT);
		// array_ = reinterpret_cast<void**>((*allocator)());
		array_ = (void**)SystemAlloc(alignSize >> PAGE_SHIFT);
		memset(array_, 0, sizeof(void*) << BITS);
	}
	// Return the current value for KFY, Returns NULL if not yet set,
	// or if k is out of range
	void* get(Number k) const {
		if ((k >> BITS) > 0) {
			return NULL;
		}
		return array_[k];
	}

	void set(Number k, void* v) {
		array_[k] = v;
	}
	
};


template <int BITS>
class TCMalloc_PageMap2 {
private:
	static const int ROOT_BITS = 5;
	static const int ROOT_LENGTH = 1 << ROOT_BITS;

	static const int LEAF_BITS = BITS - ROOT_BITS;
	static const int LEAF_LENGTH = 1 << LEAF_BITS;

	struct Leaf {
		void* values[LEAF_LENGTH];
	};
	Leaf* root_[ROOT_LENGTH];
	void* (*allocator_)(size_t);
public:
	typedef uintptr_t Number;
	// explicit TCMalloc_PageMap2(void* (*allocator)(size_t))
	explicit TCMalloc_PageMap2() {
		memset(root_, 0, sizeof(root_));
		void PreallocateMoreMemory();
	}
	void* get(Number k) const {
		const Number i1 = k >> LEAF_BITS;
		const Number i2 = k & (LEAF_LENGTH - 1);
		if ((k >> BITS) > 0 || root_[i1] == NULL) {
			return NULL;
		}
		return root_[i1]->values[i2];
	}

	void set(Number k, void* v) {
		const Number i1 = k >> LEAF_BITS;
		const Number i2 = k & (LEAF_LENGTH - 1);
		assert(i1 < ROOT_LENGTH);
		root_[i1]->values[i2] = v;
	}

	bool Ensure(Number start, size_t n) {
		for (Number key = start; key <= start + n - 1;) {
			const Number i1 = key >> LEAF_BITS;

			// check for overflow
			if (i1 >= ROOT_LENGTH) {
				return false;
			}

			// Make 2nd level node if necessary
			if (root_[i1] == NULL) {
				// Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
				// if (leaf == NULL) return false;
				static ObjectPool<Leaf> LeafPool;
				Leaf* leaf = (Leaf*)LeafPool.New();
				memset(leaf, 0, sizeof(*leaf));
				root_[i1] = leaf;
			}

			// Advance key past whatever is covered by this leaf node
			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
		}
		return true;
	}

	void PreallocateMoreMemory() {
		// Allocate enough to keep track of all possible pages
		Ensure(0, 1 << BITS);
	}

};














